
/////////////////////////////////////////////////////////////////////////////////
//
//  线性表 ： https://www.cnblogs.com/choon/p/3876606.html
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>

const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:

    SeqList()                       //无参数构造方法
    {
        length = 0;
    }

    SeqList(DataType a[], int n)     //有参数构造方法
    {
        if(n>MaxSize) throw "wrong parameter";
        for(int i=0;i<n;i++)
        {
            data[i]=a[i];
        }
        length = n;
    }

    ~SeqList(){}                    // 析构函数
    int Length(){return length;}    // 线性表长度

    DataType Get(int i)             //取出在位置 i 的元素
    {
        if(i<0 || i>length-1)
            throw "invalid Location";
        else
            return data[i];
    }

    int Find(DataType target)            // 按值查找所在位置，并返回
    {
        int pos = -1;
        for (int i = 0; i < length - 1;i++)
        {
            if(target==data[i])
            {
                pos = i;
                break;
            }
        }
        return pos;
    }

    void Insert(int i, DataType target)   // 位置 i 插入元素 target
    {
        if( i<0 || i>length-1 )  throw "invalid Location";
        if( length > MaxSize ) throw "no space !";
        for(int j=length; j>i; j--)
        {
            data[j] = data[j - 1];
        }
        data[i] = target;

        length++;
    }

    DataType RemoveAt(int i)          // 删除位置i的元素
    {
        if( i<0 || i>length-1 )  throw "invalid Location";
        auto target = data[i];
        for (; i < length - 1;i++)
        {
            data[i] = data[i + 1];
        }
        length--;
        return target;
    }

    void ToString()                // 遍历显示list 元素
    {
        std::cout << "length = " << length << std::endl;
        for (int i = 0; i < length;i++)
        {
            std::cout << data[i];
        }
        std::cout << std::endl;
    }

private:
    DataType data[MaxSize];         // 顺序表使用数组实现
    int length;                     // 存储顺序表的长度
};


int main()
{
    SeqList<int> lst;
    lst.ToString();
    // 插入10个数字给线性表list`
    for (int i = 0; i < 10; i++)
    {
        lst.Insert(i,i);
    }
    lst.ToString();
    return EXIT_SUCCESS;
}

